package com.wcj.tree;

import javax.swing.*;

public class 二叉搜索树 {


    // 查找递归
    TreeNode find(TreeNode root,int data){
        if (root == null){
            return null;
        }
        if (data < root.val){
            return find(root.left,data);
        }else if (data > root.val){
            return find(root.right,data);
        }
        return root;
    }

    // 查找非递归
    TreeNode findNonRecur(TreeNode root, int data){
        if (root == null){
            return null;
        }
        while (root != null){
            if (data == root.val){
                return root;
            }else if (data > root.val){
                root = root.right;
            }else
                root = root.left;
        }
        return null;
    }

    // 找最小递归
    TreeNode findMin(TreeNode root){
        if (root == null){
            return null;
        }
        else
            if (root.left == null)
                return root;
            else return findMin(root.left);
    }
    // 找最小非递归
    TreeNode findMinNonRecur(TreeNode root){
        if (root == null){
            return null;
        } else{
            while (root.left != null){
                root = root.left;
            }
        }
        return root;
    }

    // 找最大递归
    TreeNode findMax(TreeNode root){
        if (root == null){
            return null;
        }else {
            if (root.right == null){
                return root;
            }else {
                return findMin(root.right);
            }
        }
    }

    // 找最大非递归
    TreeNode findMaxNonRecur(TreeNode root){
        if (root == null){
            return null;
        }else {
            while (root.right != null){
                root = root.right;
            }
            return root;
        }
    }

    // 插入
    TreeNode insert(TreeNode root,int data){
        if (root == null){
            root = new TreeNode(data);
        }else {
            if (data < root.val) {
                root.left = insert(root.left,data);
            }else if (data > root.val){
                root.right = insert(root.right,data);
            }
        }
        return root;
    }

    // 删除
    TreeNode delete(TreeNode root,int data){
        TreeNode tmp;
        if (root == null){
            System.out.println("tree is empty");
        }else if (data < root.val){
            root.left = delete(root.left,data);
        }else if (data > root.val){
            root.right = delete(root.right,data);
        }else {
            if (root.left != null && root.right != null){
                // 要删除的节点有两个儿子，就用左子树最大的代替
                tmp = findMax(root.left);
                root.val = tmp.val;
                root.left = delete(root.left,root.val);
            }else {
                tmp = root;
                if (root.left == null){
                    root = root.right;
                }
                if (root.right == null){
                    root = root.left;
                }
            }
        }
        return root;
    }















}
